package main.old.old_2022;


/**
 * @Author: Take-off
 * @Description: //TODO
 * 733. 图像渲染
 * 200. 岛屿数量
 *
 * @Date: 8:20 PM 2022/7/26
 * @Param:
 * @return:
 **/

public class Solution0726 {

    //图像渲染
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
// 先记录当前像素点的值，用作后面的判断
        int curColor = image[sr][sc];
        // 若初始像素跟要修改的相同，不需要修改直接返回
        if (curColor == newColor) {
            return image;
        }
        // 要先修改像素再进入下面递归的判断
        // 相当于标记当前像素点已被遍历过，否则相当于死循环，跳不出递归
        image[sr][sc] = newColor;
        if (sr - 1 >= 0 && image[sr - 1][sc] == curColor) {
            floodFill(image, sr-1, sc, newColor);
        }
        if (sr + 1 < image.length && image[sr + 1][sc] == curColor) {
            floodFill(image, sr+1, sc, newColor);
        }
        if (sc - 1 >= 0 && image[sr][sc - 1] == curColor) {
            floodFill(image, sr, sc-1, newColor);
        }
        if (sc + 1 < image[0].length && image[sr][sc + 1] == curColor) {
            floodFill(image, sr, sc+1, newColor);
        }
        return image;
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }

    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

}
